令 为工厂 到工厂 （山底）的距离， 为在第 个工厂建仓库的最小花费。
因为只能向下运，所以第 个工厂必须建仓库存放它自己的产品，答案便为
边界条件 为不建仓库的花费。
那么有转移：
设有两决策点 , 且 优于
注意到 是递减的，但 是递增的，所以正常维护一个下凸包就行了。
#include <cstdio>
#define LL long long
const int MAXN = 1e6;
int n , d[ MAXN + 5 ] , c[ MAXN + 5 ];
LL dp[ MAXN + 5 ] , p[ MAXN + 5 ];
int Que[ MAXN + 5 ] , Head , Tail;
LL fx( int i ) { return p[ i ]; }
LL fy( int i ) { return dp[ i ]; }
LL deltax( int i , int j ) { return fx( i ) - fx( j ); }
LL deltay( int i , int j ) { return fy( i ) - fy( j ); }
int main( ) {
scanf("%d",&n);
for( int i = 1 ; i <= n ; i ++ )
scanf("%d %lld %d",&d[ i ],&p[ i ],&c[ i ]) , p[ i ] += p[ i - 1 ];
for( int i = 1 ; i <= n ; i ++ ) d[ i ] = d[ n ] - d[ i ];
for( int i = 1 ; i <= n ; i ++ ) dp[ 0 ] += d[ i ] * ( p[ i ] - p[ i - 1 ] );
Head = 1 , Tail = 0; Que[ ++ Tail ] = 0;
for( int i = 1 ; i <= n ; i ++ ) {
for( ; Head < Tail && deltay( Que[ Head ] , Que[ Head + 1 ] ) >= -d[ i ] * deltax( Que[ Head ] , Que[ Head + 1 ] ) ; Head ++ );
dp[ i ] = dp[ Que[ Head ] ] - ( p[ i ] - p[ Que[ Head ] ] ) * d[ i ] + c[ i ];
for( ; Head < Tail && deltay( Que[ Tail - 1 ] , Que[ Tail ] ) * deltax( Que[ Tail ] , i ) >= deltay( Que[ Tail ] , i ) * deltax( Que[ Tail - 1 ] , Que[ Tail ] ) ; Tail -- );
Que[ ++ Tail ] = i;
}
printf("%lld\n", dp[ n ] );
return 0;
}